package leecode.topk;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author wangxi created on 2021/5/15 23:59
 * @version v1.0
 *
 * https://www.nowcoder.com/questionTerminal/fd711bdfa0e840b381d7e1b82183b3ee
 */
public class TopKstrings {

    public static void main(String[] args) {
        String[] strings = {"abcd","abcd","abcd","pwb2","abcd","pwb2","p12"};
        TopKstrings obj = new TopKstrings();
        String[][] res = obj.topKstrings(strings, 3);

        for (String[] item : res) {
            System.out.println(Arrays.toString(item));
        }
    }

    public String[][] topKstrings (String[] strings, int k) {
        // write code here
        if (strings == null || strings.length <= 0) {
            return new String[0][0];
        }
        Map<String, Integer> dict = new HashMap<>();
        for (String s : strings) {
            dict.put(s, dict.getOrDefault(s, 0) + 1);
        }
        // 堆的排序是保留哪些元素
        // 建立次数最小堆, 并且建立 字典排序大堆，把asc码大的poll掉，注意最大堆peek元素(root节点)是最大的
        PriorityQueue<String> queue = new PriorityQueue<>((o1, o2) -> {
            if (dict.get(o1).equals(dict.get(o2)) ) {
                // 这里本应该是 o1.compareTo(o2) 小到大排序
                return o2.compareTo(o1);
            } else {
                return Integer.compare(dict.get(o1), dict.get(o2));
            }
        });
        // 注意：使用的是dict.keySet()，使用原来的words数据会有问题
        // 原始words数组会有重复元素，比如出现次数最大的单词出现了k次，那么会堆中保留k个元素，这是错误的。
        // 每个单词在堆中只能出现一次
        for (String s : dict.keySet()) {
            queue.offer(s);
            if (queue.size() > k) {
                // 自动弹出最小元素
                queue.poll();
            }
        }
        String[][] res = new String[queue.size()][2];
        // 堆可以这样遍历，这种是小到大排序
        List<String> list = new ArrayList<>();
        while (!queue.isEmpty()) {
            list.add(queue.poll());
        }
        // 不能使用list.sort按照次数排序，因为从堆中获取的是按照指定规则排序的倒序，
        // 如果下面仅仅使用次数排序，在元素次数相同时就会出现问题。
        //list.sort((o1, o2) -> Integer.compare(dict.get(o2), dict.get(o1)));
        Collections.reverse(list);
        for (int i = 0; i < list.size(); i++) {
            res[i][0] = list.get(i);
            res[i][1] = dict.get(list.get(i)) + "";
        }
        return res;
    }
}
